package leetcode;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeLevelOrderTraversal102 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Node<E> {
        E val;
        Node next;

        public Node(E val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    class LinkedListQueue<E> {
        Node head = new Node(null, null);
        Node tail = head;

        {
            tail.next = head;
        }

        public void offer(E val) {
            Node added = new Node(val, head);
            tail.next = added;
            tail = added;
        }

        public E poll() {
            Node first = head.next;
            head.next = first.next;
            if (head == first.next) {
                tail = head;
            }
            return (E) first.val;
        }

        public boolean isEmpty() {
            return head == tail;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);
        List<List<Integer>> list = new ArrayList();
        int c1 = 1;
        while (!queue.isEmpty()) {
            List<Integer> elements = new ArrayList();
            int c2 = 0;
            for (int i = 0; i < c1; i++) {
                TreeNode node = queue.poll();
                elements.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                    c2++;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    c2++;
                }
            }
            c1 = c2;
            list.add(elements);
        }
        return list;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                3,
                new TreeNode(9, new TreeNode(12, null, null), new TreeNode(4)),
                new TreeNode(20, new TreeNode(15), new TreeNode(7))
        );
        BinaryTreeLevelOrderTraversal102 t = new BinaryTreeLevelOrderTraversal102();
        t.levelOrder(root);
    }
}
